/**
 * 在英语中，我们有一个叫做词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为继承词(successor)。例如，词根an，跟随着单词other(其他)，可以形成新的单词another(另一个)。
 *
 * 现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
 *
 * 你需要输出替换之后的句子。
 *
 * 链接：https://leetcode.cn/problems/replace-words
 * 思路：前缀树
 * 详解：https://labuladong.gitee.io/algo/2/23/61/
 */
class ReplaceWords {
    public String replaceWords(List<String> dictionary, String sentence) {
        TrieMap<Integer> map=new TrieMap<>();
        for(String key:dictionary) {
            map.put(key,1);
        }
        StringBuilder sb=new StringBuilder();
        String[] words=sentence.split(" ");
        for(int i=0;i<words.length;i++) {
            String prefix=map.shortestPrefixOf(words[i]);
            if(!prefix.isEmpty()) {
                sb.append(prefix);
            } else {
                sb.append(words[i]);
            }
            if(i!=words.length-1) {
                sb.append(" ");
            }
        }
        return sb.toString();
    }
}
class TrieMap<V> {
    //ASCII码个数
    private static final int R=256;
    //当前存在Map中的键值对个数
    private int size=0;
   private static class TrieNode<V> {
       V val=null;
       TrieNode<V>[] children=new TrieNode[R];
   }
   private TrieNode<V> root=null;
   public TrieMap() {
       root=new TrieNode<V>();
   }
   //从节点node开始搜索key，如果存在返回对应节点，如果没有，返回null
   private TrieNode<V> getNode(TrieNode<V> node,String key) {
        int len=key.length();
        TrieNode<V> p=node;
        for(int i=0;i<len;i++) {
            if(p==null) {
                return null;
            }
            char c=key.charAt(i);
            p=p.children[c];
        }
        return p;
   }
   //搜索key对应的值，不存在则返回null
   public V get(String key) {
        TrieNode<V> p=getNode(root,key);
        if(p==null||p.val==null) {
            return null;
        }
        return p.val;
   }
   //判断key是否存在于树中
   public boolean containsKey(String key) {
       return get(key)!=null;
   }
   //判断是否存在前缀为prefix的键
   public boolean hasKeyWithPrefix(String prefix) {
        return getNode(root,prefix)!=null;
   }
   //在所有键中寻找query的最短前缀
   public String shortestPrefixOf(String query) {
        TrieNode<V> p=root;
        int len=query.length();
        for(int i=0;i<len;i++) {
            if(p==null) {
                return "";//如果p==null，返回空串
            }
            if(p.val!=null) {
                return query.substring(0,i);
            }
            char c=query.charAt(i);
            p=p.children[c];
        }
        if(p!=null&&p.val!=null) {
            return query;
        }
        return "";
   }
   //在所有键中寻找query的最长前缀
    public String longestPrefixOf(String query) {
        int len=query.length();
        TrieNode<V> p=root;
        int max=0;
        for(int i=0;i<len;i++) {
            if(p==null) {
                break;
            }
            if(p.val!=null) {
                max=i;
            }
            char c=query.charAt(i);
            p=p.children[c];
        }
        if(p!=null&&p.val!=null) {
            return query;
        }
        return query.substring(0,max);
    }
    //搜索所有前缀为prefix的键
    public List<String> keysWithPrefix(String prefix) {
        List<String> ret =new ArrayList<>();
        TrieNode<V> x=getNode(root,prefix);
        if(x==null) {
            return ret;
        }
        travel(x,new StringBuilder(prefix),ret);
        return ret;
    }
    private void travel(TrieNode<V> node,StringBuilder path,List<String> ret) {
       if(node==null) {
           return;
       }
       if(node.val!=null) {
           ret.add(path.toString());
       }
       for(char i=0;i<R;i++) {
           path.append(i);
           travel(node.children[i],path,ret );
           path.deleteCharAt(path.length()-1);
       }
    }
    //搜索有通配符.,搜索所有匹配的键
    public List<String> keysWithPattern(String pattern) {
       List<String> ret=new ArrayList<>();
       TrieNode<V> x=getNode(root,pattern);
       if(x==null) {
           return ret;
       }
       travel(x,new StringBuilder(),pattern,0,ret);
       return ret;
    }
    private void travel(TrieNode<V> node,StringBuilder path,String pattern,int i,List<String> ret) {
       if(node==null) {
           return;
       }
       if(i==pattern.length()) {
           if(node.val!=null) {
               ret.add(path.toString());
           }
           return;
       }
       char c=pattern.charAt(i);
       if(c=='.') {
           for(char j=0;j<R;j++) {
               path.append(j);
               travel(node.children[j],path,pattern,i+1,ret );
               path.deleteCharAt(path.length()-1);
           }
       } else {
            path.append(c);
            travel(node.children[c],path,pattern,i+1,ret );
       }
    }
    //通配符.搜索是否存在匹配的键
    public boolean hasKeyWithPattern(String pattern) {
        return hasKeyWithPattern(root,pattern,0);
    }
    public boolean hasKeyWithPattern(TrieNode<V> node,String pattern,int i) {
       if(node==null) {
           return false;
       }
       if(i==pattern.length()) {
           return node.val!=null;
       }
       char c=pattern.charAt(i);
       if(c!='.') {
           return hasKeyWithPattern(node.children[c],pattern,i+1);
       }
       for(char j=0;j<R;j++) {
           if(hasKeyWithPattern(node.children[j],pattern,i+1)) {
               return true;
           }
       }
       return false;
    }
    //给前缀树添加键值对
    public void put(String key,V val) {
       if(!containsKey(key)) {
           size++;
       }
       root=put(root,key,val,0);
    }
    private TrieNode<V> put(TrieNode<V> node ,String key,V val,int i) {
       if(node==null) {
           node=new TrieNode<>();
       }
       if(key.length()==i) {
           node.val=val;
           return node;
       }
       char c=key.charAt(i);
       node.children[c]=put(node.children[c],key,val,i+1);
       return node;
    }
    //返回前缀树中键值对的数量
    public int size() {
       return this.size;
    }
    //删除前缀树中的key
    public void remove(String key) {
       if(!containsKey(key)) {
           return;
       }
       root=remove(root,key,0);
       size--;
    }
    public TrieNode<V> remove(TrieNode<V> node,String key,int i) {
       if(node==null) {
           return null;
       }
       if(i==key.length()) {
           node.val=null;
       } else {
           char c=key.charAt(i);
           node.children[c]=remove(node.children[c],key,i+1);
       }
       //后序位置，递归路径上节点可能需要被清理
       if(node.val!=null) {
           //如果该节点存储着val，则不需要被清理
           return node;
       }
       //检查改TrieNode是否还有后缀
       for(int c=0;c<R;c++) {
           if(node.children[c]!=null) {
               return node;//只要还有一个子节点（后缀树枝）就不需要被清理
           }
       }
       //没有存储val,也没有后缀树枝，则该节点要被清理
       return null;
    }
}